function insertSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    for (let i = 1; i < arr.length; i ++) {
        let j = i - 1
        let temp = arr[i]
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = temp
    }
    return arr
}
function bucketSort(arr,bucketSize = 3) {
    //? 1. 找到最大最小值 根据这个分桶(类似于计数排序)
    let min = Infinity
    let max = -Infinity
    for (let i = 0; i < arr.length; i ++) {
        if (arr[i] < min) min = arr[i]
        if (arr[i] > max) max = arr[i]
    }
    //? 计算桶的个数
    const bucketCount = Math.floor((max - min + 1) / bucketSize) + 1
    //? 创建桶
    const buckets = new Array(bucketCount).fill(0).map(() => [])
    //? 为每个数分到相应的桶
    for (let i = 0; i < arr.length; i ++) {
        buckets[Math.floor((arr[i] - min) / bucketSize)].push(arr[i])
    }
    //? 对每个桶进行插入排序
    let startIndex = 0
    for (let i = 0; i < buckets.length; i ++) {
        if (buckets[i].length > 0) {
            insertSort(buckets[i])
            //? 给原数组重新赋值
            for (let j = 0; j < buckets[i].length; j++) {
                arr[startIndex + j] = buckets[i][j]
            }
            startIndex += buckets[i].length
        }
    }
    return arr
}
const arr = [5,2,6,1,7,2,10,8]
console.log(bucketSort(arr))
